package leetcode.editor.cn;

//给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。 
//
// 示例 1: 
//
// 输入: num1 = "2", num2 = "3"
//输出: "6" 
//
// 示例 2: 
//
// 输入: num1 = "123", num2 = "456"
//输出: "56088" 
//
// 说明： 
//
// 
// num1 和 num2 的长度小于110。 
// num1 和 num2 只包含数字 0-9。 
// num1 和 num2 均不以零开头，除非是数字 0 本身。 
// 不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理。 
// 
// Related Topics 数学 字符串 模拟 👍 790 👎 0

import java.util.Arrays;

//Java：字符串相乘
public class MultiplyStrings_43 {
    public static void main(String[] args) {
        Solution solution = new MultiplyStrings_43().new Solution();
        // TO TEST
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public String multiply(String num1, String num2) {
            if (num1.equals("0") || num2.equals("0")) return "0";
            int len1 = num1.length(), len2 = num2.length();
            String[] nums = new String[len2];
            for (int i = 0; i < len2; i++) { //逐位相乘
                StringBuffer sb = new StringBuffer();
                int y = num2.charAt(len2 - i - 1) - '0', carry = 0;
                for (int j = 0; j < i; j++) {
                    sb.append(0);
                }
                for (int j = len1 - 1; j >= 0; j--) {
                    int x = num1.charAt(j) - '0';
                    int mul = x * y + carry;
                    sb.append(mul % 10);
                    carry = mul / 10;
                }
                if (carry > 0) sb.append(carry);
                nums[i] = sb.reverse().toString();
            }
            System.out.println(Arrays.toString(nums));
            StringBuffer res = new StringBuffer();
            for (int i = 1; i < len2; i++) {
                nums[i] = addStrings(nums[i - 1], nums[i]);
            }
            return nums[len2 - 1];
        }

        public String addStrings(String num1, String num2) {
            int len1 = num1.length(), len2 = num2.length(), carry = 0;
            StringBuffer sb = new StringBuffer();
            for (int i = 0; i < Math.max(len1, len2); i++) {
                int x = i < len1 ? num1.charAt(len1 - i - 1) - '0' : 0;
                int y = i < len2 ? num2.charAt(len2 - i - 1) - '0' : 0;
                int res = x + y + carry;
                sb.append(res % 10);
                carry = res / 10;
            }
            if (carry > 0) sb.append(carry);
            return sb.reverse().toString();
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
